#include <stdio.h>
#include "polygon.h"

#define FP_SCALE 10000LL  // 定点放大因子

// 内部高精度计算使用的结构体
typedef struct {
    long long x;
    long long y;
} point_fp_t;

// 判断点 p 是否在由边 A->B 定义的裁剪半平面内部（约定：边的左侧为内部）
static int inside(point_fp_t p, point_fp_t A, point_fp_t B)
{
    long long cross_val = (B.x - A.x) * (p.y - A.y) - (B.y - A.y) * (p.x - A.x);
    return cross_val >= 0;
}

// 计算向量差：返回 a - b
static point_fp_t subtract(point_fp_t a, point_fp_t b)
{
    point_fp_t r;
    r.x = a.x - b.x;
    r.y = a.y - b.y;
    return r;
}

// 计算向量叉积：a x b
static long long cross(point_fp_t a, point_fp_t b)
{
    return a.x * b.y - a.y * b.x;
}

/*
 * 计算直线段 s->e 与直线（由 A->B 定义）的交点。
 * 利用公式： t = cross(A - s, A - B) / cross(e - s, A - B)
 * 为避免浮点数运算，t 以定点形式表示（范围 0~FP_SCALE）。
 * 交点 = s + t*(e-s)
 */
static point_fp_t computeIntersection(point_fp_t s, point_fp_t e, point_fp_t A, point_fp_t B)
{
    point_fp_t se = subtract(e, s);
    long long num = cross(subtract(A, s), subtract(A, B));
    long long denom = cross(se, subtract(A, B));
    long long t_fixed = (num * FP_SCALE) / denom;  // t 的定点值
    point_fp_t inter;
    inter.x = s.x + (se.x * t_fixed) / FP_SCALE;
    inter.y = s.y + (se.y * t_fixed) / FP_SCALE;
    return inter;
}

/*
 * 对多边形 inPoly（共 inCount 个顶点，使用高精度坐标）按裁剪边 A->B 进行裁剪，
 * 将结果存入 outPoly，并返回输出顶点数。
 */
static int clipPolygonEdge(point_fp_t inPoly[], int inCount, point_fp_t A, point_fp_t B, point_fp_t outPoly[])
{
    if (inCount == 0)
        return 0;
    int outCount = 0;
    // 令 s 为多边形的最后一个顶点
    point_fp_t s = inPoly[inCount - 1];
    int s_inside = inside(s, A, B);
    for (int i = 0; i < inCount; i++) {
        point_fp_t p = inPoly[i];
        int p_inside = inside(p, A, B);
        if (p_inside) {
            if (!s_inside) {
                point_fp_t inter = computeIntersection(s, p, A, B);
                outPoly[outCount++] = inter;
            }
            outPoly[outCount++] = p;
        }
        else {
            if (s_inside) {
                point_fp_t inter = computeIntersection(s, p, A, B);
                outPoly[outCount++] = inter;
            }
        }
        s = p;
        s_inside = p_inside;
    }
    return outCount;
}

/*
 * 计算多边形 poly 与矩形 rect 的交集面积与矩形面积的比值。
 *
 * 参数：
 *    poly   - 指向多边形顶点数组的指针（point_t 数组，点坐标均为 int 类型）
 *    poly_n - 多边形顶点数
 *    rect   - 矩形（rect_t 结构体，成员：x, y, width, height）
 *
 * 返回：
 *    交集面积与矩形面积的比例（double 类型），若交集区域顶点不足 3 个，则返回 0.0。
 */
double computeIntersectionRatio(const point_t *poly, int poly_n, const rect_t *rect)
{
    // 将多边形转换为高精度坐标（乘以 FP_SCALE）
    point_fp_t polyFP[100];  // 假定多边形最多 100 个顶点
    for (int i = 0; i < poly_n; i++) {
        polyFP[i].x = (long long)poly[i].x * FP_SCALE;
        polyFP[i].y = (long long)poly[i].y * FP_SCALE;
    }

    // 根据 rect_t 生成矩形的 4 个顶点，按顺时针或逆时针排列（此处取：左上、右上、右下、左下）
    point_t rectPoints[4];
    rectPoints[0].x = rect->x;
    rectPoints[0].y = rect->y;
    rectPoints[1].x = rect->x + rect->width;
    rectPoints[1].y = rect->y;
    rectPoints[2].x = rect->x + rect->width;
    rectPoints[2].y = rect->y + rect->height;
    rectPoints[3].x = rect->x;
    rectPoints[3].y = rect->y + rect->height;

    // 将矩形顶点转换为高精度坐标
    point_fp_t rectFP[4];
    for (int i = 0; i < 4; i++) {
        rectFP[i].x = (long long)rectPoints[i].x * FP_SCALE;
        rectFP[i].y = (long long)rectPoints[i].y * FP_SCALE;
    }

    // 利用 Sutherland-Hodgman 裁剪算法，将多边形裁剪到矩形内部
    point_fp_t clipPoly1[200], clipPoly2[200];
    int subjectCount = poly_n;
    for (int i = 0; i < subjectCount; i++) {
        clipPoly1[i] = polyFP[i];
    }
    for (int i = 0; i < 4; i++) {
        point_fp_t A = rectFP[i];
        point_fp_t B = rectFP[(i + 1) % 4];
        int outCount = clipPolygonEdge(clipPoly1, subjectCount, A, B, clipPoly2);
        subjectCount = outCount;
        for (int j = 0; j < subjectCount; j++) {
            clipPoly1[j] = clipPoly2[j];
        }
    }

    // 用鞋带公式计算交集多边形的面积×2（高精度值）
    long long interArea2 = 0;
    if (subjectCount < 3) {
        interArea2 = 0;
    }
    else {
        for (int i = 0; i < subjectCount; i++) {
            int j = (i + 1) % subjectCount;
            interArea2 += clipPoly1[i].x * clipPoly1[j].y - clipPoly1[j].x * clipPoly1[i].y;
        }
        if (interArea2 < 0)
            interArea2 = -interArea2;
    }

    // 计算矩形的面积×2（高精度值），同样使用鞋带公式
    long long rectArea2 = 0;
    for (int i = 0; i < 4; i++) {
        int j = (i + 1) % 4;
        rectArea2 += rectFP[i].x * rectFP[j].y - rectFP[j].x * rectFP[i].y;
    }
    if (rectArea2 < 0)
        rectArea2 = -rectArea2;
    if (rectArea2 == 0)
        return 0.0;

    // 交集和矩形面积均包含了相同的放大因子与 2 的因子，直接相除得到比值
    double ratio = (double)interArea2 / (double)rectArea2;
    return ratio;
}

// 示例主函数，演示如何调用 computeIntersectionRatio 函数
// int main()
// {
//     point_t polygon[5] = {
//         {1, 1}, {5, 1}, {5, 4}, {3, 3}, {1, 4}};
//     int poly_n = 5;

//     rect_t rectangle = {2, 2, 4, 3};  // 矩形：左上角 (2,2)，宽 4，高 3

//     double ratio = computeIntersectionRatio(polygon, poly_n, &rectangle);
//     printf("交集面积与矩形面积的比值为: %.4f\n", ratio);

//     return 0;
// }
